/**
* @description: 97. 交错字符串
* @author hewei
* @date 2022/7/25 16:23
* @version 1.0
*/

public class IsInterleave {

    public static void main(String[] args) {
        IsInterleave isInterleave = new IsInterleave();
        System.out.println(isInterleave.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
    }

    String s1;
    String s2;
    public boolean isInterleave1(String s1, String s2, String s3) {
        this.s1 = s1;
        this.s2 = s2;
        if (s1.length() + s2.length() != s3.length()) return false;
        return dfs(s3.toCharArray(), 0, 0);
    }

    public boolean dfs(char[] target, int i, int curTarget) {
        if (i == target.length || curTarget == s1.length()) {
            if (curTarget < s1.length()) return false;
            if (new String(target).replaceAll("#", "").equals(s2)) return true;
            return false;
        }
        if (s1.length() - curTarget > target.length - i) return false;
        if (!new String(target, 0, i).replaceAll("#", "")
                .equals(s2.substring(0, i - curTarget))) return false;

        char temp = s1.charAt(curTarget);
        if (temp != target[i]) return dfs(target, i + 1, curTarget);
        if (dfs(target, i + 1, curTarget)) return true;
        target[i] = '#';
        boolean res = dfs(target, i + 1, curTarget + 1);
        target[i] = temp;
        return res;
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) return false;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i < m + 1; i++) {
            if (s1.charAt(i - 1) != s3.charAt(i - 1)) break;
            dp[i][0] = true;
        }
        for (int i = 1; i < n + 1; i++) {
            if (s2.charAt(i - 1) != s3.charAt(i - 1)) break;
            dp[0][i] = true;
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                char c1 = s1.charAt(i - 1);
                char c2 = s2.charAt(j - 1);
                char c3 = s3.charAt(i - 1 + j);
                char c4 = s3.charAt(i + j - 2);
                if ((dp[i - 1][j] && c1 == c3) || (dp[i][j - 1] && c2 == c3) || (dp[i - 1][j - 1] && c4 + c3 == c1 + c2 && c4 - c3 == c1 - c2)) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[m][n];
    }
}
